package com.itzmn.newcode.offer1;

import java.util.Collections;

/**
 * @Author: 张梦楠
 * @Date: 2018/12/20 16:51
 * 简书：https://www.jianshu.com/u/d611be10d1a6
 * 码云：https://gitee.com/zhangqiye
 * @Description: 复杂链表的复制
 *
 *  输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），
 *  返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
 *
 *   1,2,3,4,5
 *   1指向3 2指向5
 *  思路：1.将所有链表节点复制一份在其后面 11其实是1，为了区分拷贝
 *          1,11,2,22,3,33,4,44,5,55
 *       2.根据原来链表节点指向的任意节点，修改复制节点的任意节点
 *          将11指向33将22指向55
 *       3.将复制链表拆下来
 *        11,22,33,44,55
 *
 */
public class _25_ReplicationOfComplexLinkedLists {
    public static void main(String[] args) {

        new _25_ReplicationOfComplexLinkedLists().test();
    }

    private void test() {

        RandomListNode init = init();
        RandomListNode clone = Clone(init);
        while (clone != null){
            System.out.println(clone.label + ".next =" + clone.next);
            System.out.println(clone.label + ".random =" + clone.random);
            clone = clone.next;
        }

    }

    public RandomListNode Clone(RandomListNode pHead) {
        //1. 复制链表节点
        RandomListNode tempHead = pHead;
        if (pHead == null){
            return null;
        }

        while (pHead != null){

            RandomListNode randomListNode = new RandomListNode(pHead.label);
            randomListNode.next = pHead.next;
            pHead.next = randomListNode;

            pHead = randomListNode.next;
        }

        //2. 将节点的随机指针加上。

        RandomListNode temp = tempHead;
        while (tempHead != null){

            RandomListNode random = tempHead.random;
            // 如果当前有随机指针，那么将下一个节点的随机指针设置为随机指针的下一个节点
            if (random != null){
                tempHead.next.random = random.next;
            }
            tempHead = tempHead.next.next;
        }

        RandomListNode tempH = temp;
        RandomListNode next = temp.next;
        RandomListNode retuHead = next;
        //2. 将节点拆掉

        while (temp.next.next != null){

            temp.next = temp.next.next;
            next.next = next.next.next;

            temp = temp.next;
            next = next.next;
        }

        temp.next = null;
        return retuHead;
    }

    private RandomListNode init(){

        RandomListNode randomListNode1 = new RandomListNode(1);
        RandomListNode randomListNode2 = new RandomListNode(2);
        RandomListNode randomListNode3 = new RandomListNode(3);
        RandomListNode randomListNode4 = new RandomListNode(4);
        RandomListNode randomListNode5 = new RandomListNode(5);

        // 顺序链表，任意指针，1指向3，2指向5
        randomListNode1.next = randomListNode2;
        randomListNode1.random = randomListNode3;
        randomListNode2.next = randomListNode3;
        randomListNode2.random = randomListNode5;
        randomListNode3.next = randomListNode4;
        randomListNode4.next = randomListNode5;

        return randomListNode1;
    }
    public class RandomListNode {
        int label;
        RandomListNode next = null;
        RandomListNode random = null;

        RandomListNode(int label) {
            this.label = label;
        }
    }

}
